package fermat_test

import (
	"fmt"
)

type tFermatTester struct {
	iFailedCount int
	iPassedCount int
}

func newFermatTester() IPrimeTester {
	return &tFermatTester{}
}

var gSamples = genSamples(3, 10)
var gSampleCount = len(gSamples)

func genSamples(from, to int) []int {
	items := make([]int, to - from + 1)
	for i := from;i<=to;i++ {
		items[i - from] = i
	}
	return items
}
func (me *tFermatTester) IsPrime(x int) bool {
	if x > 0x7fffffff {
		panic("too large number, max 0x7fffffff")
	}

	if x <= 1 {
		return false
	}

	if x <= 3 {
		return true
	}

	for i:= 0;i < gSampleCount;i++ {
		n := gSamples[i]
		if n >= x || n <= 1 {
			break
		}

		if !me.fermatTest(n, x) {
			me.iFailedCount++
			return false
		}
	}

	me.iPassedCount++
	return SimplePrimeTester.IsPrime(x)
}

func (me *tFermatTester) fermatTest(n int, p int) bool {
	// n^p % p == n ?
	return n == fastMod(n, p, p)
}

func fastMod(n int, p int, mod int) int {
	sum := 1
	for p > 0 {
		if (p & 1) > 0 {
			sum = (sum * n) % mod
			p--

		} else {
			p /= 2
			n = (n * n) % mod
		}
	}
	return sum
}

func (me *tFermatTester) String() string {
	return fmt.Sprintf("Fermat(fail=%v, pass=%v)", me.iFailedCount, me.iPassedCount)
}


var FermatPrimeTester = newFermatTester()